/**
 * 回文数
 *
 * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
 *
 * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
 *
 * 例如，121 是回文，而 123 不是。
 */

/**
 * 1. 中心扩散法, 选取一个中心点, 向左右两边扩散, 如果相同则继续扩散, 如果不同则不是回文数
 * 这个方法要注意数字是奇数还是偶数
 * 时间复杂度 :
 * 空间复杂度 :
 *
 * 2. 直接从外向内一个一个数字进行判断, 直到相遇, 中途遇到不相同的就不是回文数
 * 时间复杂度 :
 * 空间复杂度 :
 *
 * 3. 将要判断的数字放入一个 list中, 然后 reverse, 在转为数字, 判断两个数是否相等
 * 时间复杂度 :
 * 空间复杂度 :
 *
 * 4. 进阶之巧妙利用数字这个特性, 前面的方法都是要将原本的数字进行转化, 哪有没有什么方法可以不转化院士来的数字呢
 * 当然是有的, 咱细心观察可以发现, 如果是回文数的话, 他是可以折叠的,也就是关于中心对称,
 * 那咱是不是可以将这两半取出来然后再进行对比呢, 当然是可以的, 想到就做, 这个方法没有将原数转化, 时间复杂度肯定是优化了的
 *
 */

public class Main {

    // 1. 中心扩散法
    public boolean isPalindrome1(int x) {

        // 先将数字化为字符串
        String s = x + "";

        // 求得他的长度
        int n = s.length();

        // 寻找中心下标
        int left = 0, right = 0;

        // 判断奇偶
        if (n % 2 == 0) {

            // 偶
            left = n / 2 - 1;
            right = left + 1;
        } else {
            // 奇
            left = n / 2;
            right = left;
        }

        while (left >=0 && right < n) {

            // 如果左边与右边不相等, 就不是回文数
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }

            left--;
            right++;
        }

        return true;
    }

    //*****************************************************

    // 2.
    public boolean isPalindrome2(int x) {

        // 先将数字化为字符串
        String s = x + "";

        // 求得他的长度
        int n = s.length();

        // 定义左右下标
        int left = 0, right = n - 1;

        // 注意等于号是否要取
        // 我们先假设长度为 奇数, 则到最后 left和 right肯定是在中间下标的两侧, 最后一个下标取与不取是没有差别的
        // 再假设长度是 偶数, 则到最后两个数时, 判断后直接就 left > rigth了, 也没有必要取等
        // 所以 = 可加可不加
        while (left < right) {

            // 左右不等
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }

            left++;
            right--;

        }

        return true;
    }

    //**************************************
    // 方法三就不写了, 也是一样的思路

    // 4. 巧用数字之美
    public boolean isPalindrome(int x) {

        // 我们先排除一些特殊情况, 比如数字 < 0, 或者是以 0 结尾的数,
        // 以 0 结尾要想他是回文数, 那第一个数肯定也要是 0, 而第一个数是 0 也只有 0了
        if ( x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }

        // 定义一个数来接收一半的数, 另一半改变 x 本身就好了
        int half = 0;

        // 怎么看循环的出口呢
        // 首先咋要明白这个是分两种情况的, 因为一个数要分成两个数, 因为数的位数有奇数和偶数, 就会有两种分到的情况
        // 让咱先来考虑数位是偶数的情况
        // 偶数 : 我们要想得到的是回文数, 两个数肯定是一样的, 所以当两个数一样大时, 就可以是循环出口了
        // 奇数 : 我们得到的两个数肯定是不一样大的, 因为位数不能平均分, 所以我们一直向下进行, half 最后肯定是大于 x 的
        // 接下来就肯定哦要出循环了, 因为继续循环会让我们辛苦分的两个数差距一直变大, 及时止损
        // 要怎么判断呢, 我们要比较的是 hale % 10 与 x
        // 循环出口显而易见 half == x 或 half > x
        // 条件就很容易看出了, 就是 x > half
        while (x > half) {

            // 一半
            half = half * 10 + x % 10;

            // 另一半
            x /= 10;
        }

        // 比较, 要进行两次比较, 分为奇数和偶数, 只要一种成立就是回文数了
        return half % 10 == x || half == x;
    }

}